package dateStructure;

import java.util.Arrays;
import java.util.Scanner;

public class  Sort {
    //直接插入排序
    public static void main(String[] args) {
        int nums[] = {7, 2, 5, 14, 1, 0, 45, 9, 4};
        insertSort(nums);
        System.out.println("排序的结果为：" + Arrays.toString(nums));
    }

    private static void insertSort(int nums[]) {
        int len = nums.length;
        int num, j;
        for (int i = 1; i < len; i++) {
            if (nums[i] < nums[i - 1]) {//如果发现当前元素比他的前一个大
                //把该元素与其前一个元素交换，然后把该元素和其上一个元素的再前面那些元素去比较，找到比该元素小的一个元素前面的位置来进行插入
                num = nums[i];

                for (j = i - 1; j >= 0 && nums[j] > num; j--) {
                    //进入循环的条件为：前面的元素一定要比向后插入的元素大！即nums[j]>num，一旦遇到比插入元素小的数就停下来，开始插入
                    nums[j + 1] = nums[j];//如果满足条件的话，将前面的元素一直向前插
                }

                //j+1的原因是因为上面循环最后j多减了一次，所以要加回去
                nums[j + 1] = num;//把该元素插入到找到的位置中去
            }
        }
    }
}

class Sort1 {
    //希尔排序
    public static void main(String[] args) {
        shell MyS = new shell();
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入排序元素的个数以及增量元素的个数：");
        MyS.num = scanner.nextInt();
        MyS.addnum = scanner.nextInt();
        System.out.println("请依次输入排序元素：");
        for (int i = 0; i < MyS.num; i++) {
            MyS.nums[i] = scanner.nextInt();
        }
        System.out.println("请依次输入增量元素：");
        for (int i = 0; i < MyS.addnum; i++) {
            MyS.add[i] = scanner.nextInt();
        }
        shellSort(MyS);
        System.out.println("增量数组为：");
        for (int i = 0; i < MyS.addnum; i++) {
            System.out.print(MyS.add[i] + "\t");
        }
        System.out.println();
        System.out.println("希尔排序后数组为：");
        for (int i = 0; i < MyS.num; i++) {
            System.out.print(MyS.nums[i] + "\t");
        }
        System.out.println();
    }

    private static final int Maxnum = 107;

    private static class shell {
        int nums[] = new int[Maxnum];//定义一个数组存要排序的值
        int add[] = new int[Maxnum];//定义一个数组存增量
        int num;//排序元素的个数
        int addnum;//增量元素的个数
    }

    /**
     * @param s 要排序的数组，增量数组，及其两个数组中元素的个数
     */

    private static void shellSort(shell s) {
        int j, x;
        for (int k = 0; k < s.addnum; k++) {//第一层循环控制增量
            int add = s.add[k];//取出每次的增量

            for (int i = add; i < s.num; i++) {//第二层循环开始直接插入排序
                if (s.nums[i] < s.nums[i - add]) {
                    x = s.nums[i];//把哨兵取出

                    for (j = i - add; j >= 0 && x < s.nums[j]; j -= add) {//开始第三层循环，进行数据的交换
                        s.nums[j + add] = s.nums[j];
                    }
                    s.nums[j + add] = x;
                }
            }
            System.out.println("这次希尔排序后数组为：");
            for (int i = 0; i < s.num; i++) {
                System.out.print(s.nums[i] + "\t");
            }
            System.out.println();
        }
    }
}

class Sort2 {
    //冒泡排序
    public static void main(String[] args) {
        int nums[] = {12, 2, 16, 30, 28, 10, 17, 6, 20, 18};
        bubbleSort(nums);
        System.out.println("冒泡排序结果为：" + Arrays.toString(nums));
    }

    private static void bubbleSort(int nums[]) {
        int len = nums.length;//取出数组长度
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    public static void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Sort3 {
    //快速排序
//    2 4 0 19 33 7 100 5 11 7
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入被排序元素的个数：");
        int n = scanner.nextInt();
        int nums[] = new int[n];
        System.out.println("请依次输入被排序的元素：");
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        quickSort(nums, 0, n - 1);
        System.out.println("快速排序改良版完成后的结果为：" + Arrays.toString(nums));
    }

    private static void quickSort(int nums[], int left, int right) {
        if (left <= right) {
            int mid = position2(nums, left, right);
            quickSort(nums, left, mid - 1);
            quickSort(nums, mid + 1, right);
        }
    }

    /**
     * @param nums  要被排序的数组
     * @param left  数组的最左边元素索引
     * @param right 数组的最右边元素索引
     * @return
     */
    private static int position(int nums[], int left, int right) {
        int i = left;//将元素的最左边开始排序
        int j = right;
        int midnum = nums[left];//一开始的初始基准元素，选取最左边元素作为基准元素
        while (i < j) {
            while (i < j && midnum < nums[j]) {//如果当前j索引下的元素都大于基准元素的话就不用交换，
                // 一直走循环，j向左减
                j--;
            }
            if (i < j) {//如果当前退出循环了，然后i仍然小于j的话，说明是当前j索引下的元素<=基准元素了，则需要交换，
                swap(nums, i++, j);//交换完毕后，基准元素来到了右侧，这时候左侧的那个被交换过去的元素的索引下标+1，因为匹配完了，
            }
            while (i < j && midnum >= nums[i]) {//如果当前j索引下的元素都小于基准元素的话就不用交换，一直走循环，j向左减
                // 一直走循环，i向右加
                i++;
            }
            if (i < j) {//如果当前退出循环了，然后i仍然小于j的话，说明是当前i索引下的元素>基准元素了，则需要交换，
                swap(nums, i, j--);//交换完毕后，基准元素来到了左侧，这时候右侧的那个被交换过去的元素的索引下标-1，因为匹配完了，
            }
        }
        //退出循环则说明i和j相等了，则当前的位置为基准元素的索引下标
        return i;//返回当前基准元素的下标
    }

    /**
     * @param nums  要被排序的数组
     * @param left  数组的最左边元素索引
     * @param right 数组的最右边元素索引
     * @return
     */
    private static int position2(int nums[], int left, int right) {
        //改良版快速排序
        //简单地说就是，就是先从右往左找，找到比基准元素小的元素；然后从左往右找，找到一个比基准元素要大的元素，然后将这两个元素进行交换，
        // 这样一直下去，知道i和j相遇，这样交换次数就少了很多
        int i = left;
        int j = right;
        int midnum = nums[left];//同样取最左边元素为基准元素
        while (i < j) {
            while (i < j && midnum < nums[j]) {//从右往左找一个元素比基准元素小的
                j--;
            }
            while (i < j && midnum >= nums[i]) {//从左往右找一个元素比基准元素大的
                i++;
            }
            if (i < j) {
                swap(nums, i++, j--);
            }//找到两个元素进行交换，一个比基准元素小，一个比基准元素大，然后两个坐标同时向中间移动
        }
        //当退出循环的时候，说明当前i=j，且i索引下左边的元素都比其小，右边的元素都比其大，然后下面进行基准元素与其i位置的元素进行交换
        while (midnum < nums[i]) {
            //如果当前i索引下的元素比基准元素大的话，就开始找i左边比它小的元素和基准元素交换
            i--;//一直向左找
        }
        swap(nums, left, i);//找到后来交换
        return i;
    }

    public static void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Sort4 {
    //选择排序+堆排序
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入堆排序的元素个数：");
        int n = scanner.nextInt();
        int nums[] = new int[n];
        System.out.println("请依次输入每个元素：");
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
//        chooseSort(nums);
        heapSort(nums);
//        System.out.println("选择排序的结果为："+Arrays.toString(nums));
        System.out.println("堆排序的结果为：" + Arrays.toString(nums));
    }

    /**
     * @param nums 待排序数组
     */
    private static void chooseSort(int nums[]) {
        int min;//定义一个索引下标，用于记录每次选到的值的索引
        for (int i = 0; i < nums.length; i++) {
            min = i;//选取索引
            for (int j = i + 1; j < nums.length; j++) {//从选取到的值索引的下一个开始比较
                if (nums[min] > nums[j]) {//如果发现选中元素前面有元素比他小
                    min = j;//把比它小的那个元素的索引下标赋值到min中
                }
            }
            if (min != i) {//如果发现之前选中的值的索引在第二层循环中被改变了
                //开始交换
                swap(nums, min, i);
            }
        }
    }

    private static void heapSort(int nums[]) {
        int len = nums.length;
        for (int i = len / 2; i >= 0; i--) {//从所有节点中间的节点，即最后一个非叶子节点开始往回走
            sink(nums, i, len);//开始将每一个节点进行下沉操作
        }
        //大顶堆排序完成

        //现在开始进行最终元素的交换
        int n = len;
        while (--n > 0) {
            swap(nums, 0, n);//将第一个索引所在的元素与其后面的元素一直进行交换,交换后每次n都要-1
            sink(nums, 0, n);
        }
    }

    /**
     * @param nums 要被排序的数组
     * @param i    当前节点的索引下标
     */
    private static void sink(int nums[], int i, int n) {//用于操作节点的下沉
        while (2 * i < n) {//当前节点有双亲
            int k = 2 * i;
            if (k < n - 1 && nums[k] < nums[k + 1]) {//如果当前右节点的值比左节点更大
                k++;//将索引移动到右节点上
            }
            if (nums[i] >= nums[k]) {//如果当前双亲比其左右节点都要大
                break;//直接退出，不用进行操作
            } else {//否则的话,就要进行堆下沉了
                swap(nums, i, k);//否则将当前节点与其双亲节点的索引下标进行交换
            }
            i = k;//判断完成后，将i的位置指向交换完成的位置，进行下一次判断比较
        }
    }

    public static void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Sort5 {
    //归并排序
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int nums[] = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        mergeSort(nums, 0, nums.length - 1);
        System.out.println("归并排序结果为：" + Arrays.toString(nums));
    }

    private static void mergeSort(int nums[], int left, int right) {
        if (left < right) {
            int mid = (left + right) >> 1;//计算出每次的中间值的索引
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);//最后进行每次二分后的合并
        }
    }

    private static void merge(int nums[], int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int ans[] = new int[right - left + 1];
        int k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] < nums[j]) {//如果i索引指向的元素比j指向的小，则先放到中间数组中
                ans[k++] = nums[i++];
            } else {//否则将j索引所指向的元素放到索引中
                ans[k++] = nums[j++];
            }
        }
        //如果两个数组中还有元素的话，把剩余的元素都逐一放到在中间数组中
        while (i <= mid) {
            ans[k++] = nums[i++];
        }
        while (j <= right) {
            ans[k++] = nums[j++];
        }
        k = 0;
        for (int x = left; x <= right; x++) {//开始将中间数组中排好序的元素放回到原数组中去
            nums[x] = ans[k++];
        }
    }
}

class Sort6 {
    //基数—桶排序
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入桶排序的元素个数：");
        int n = scanner.nextInt();
        int nums[] = new int[n];
        System.out.println("请依次输入每个元素：");
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        radixSort(nums);
        System.out.println("桶排序的结果为:" + Arrays.toString(nums));
    }

    private static void radixSort(int nums[]) {
        int maxbit = findMaxbit(nums);
        System.out.println("最大的位数为："+maxbit);
        //开始初始化
        int len = nums.length;
        int rs[][] = new int[10][];//可先开第一维的空间大小,为个位上0~9个空间
        for (int i = 0; i < 10; i++) {
            rs[i] = new int[len + 1];//多开一个空间，**以为rs[i][0]是用来存当前桶中元素的个数的
        }

        //初始化完毕开始元素放入到桶中
        for (int bit = 1; bit <= maxbit; bit++) {//从第一位个位开始注意把元素放入到桶中
            for (int j = 0; j < len; j++) {//将每一个元素从数组中取出，然后将每一位数作为桶号放入到桶中
                int no = findBitnumber(nums[j], bit);//记录当前元素位数上的元素，作为桶号
                rs[no][++rs[no][0]] = nums[j]; //然后将当前桶中元素个数+1，同时将桶的个数作为其桶号，将当前元素放入桶中,
            }
            //****排序好一位之后就立马讲其放入回原数组中，并且清空rs[i][0]然后再对下一位进行排序，要是分开来的话，元素会重复，就会导致数组越界
            int k = 0;
            for (int i = 0; i < 10; i++) {//通过个位数0~9确定桶号，将里面的元素进行收集
                for (int j = 1; j <= rs[i][0]; j++) {//将桶中的元素逐一拿出
                    nums[k++] = rs[i][j];//同时放回到原数组中
                }
                rs[i][0] = 0;//每次都要讲当前桶号所在的桶中的元素个数清空
            }
        }
    }

    /**
     * @param num 要被查找位数数字的数字
     * @param bit 要查找的位数
     * @return 被查找位数上的数字
     */
    public static int findBitnumber(int num, int bit) {
        int k=1;
        while (--bit>0){
            k*=10;
        }
        return (num/k)%10;
    }

    public static int findMaxbit(int nums[]) {
        int maxnum = -1;//定义一个变量存数组中最大的数字
        for (int i : nums) {//找寻数组中最大的数字
            maxnum = Math.max(maxnum, i);
        }
        int bit = 0;
        while (maxnum != 0) {//取出最大数的位数
            bit++;
            maxnum /= 10;
        }
        return bit;
    }
}

class Sort7 {
    //优先队列的应用
    private static final int Maxsize = 107;
    private static int nums[] = new int[Maxsize];
    private static boolean tap = true;
    private static int n;

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入要入优先队列的元素个数：");
        n = scanner.nextInt();
        System.out.println("请依次输入队列中的元素：");
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        priorityQueue();
        System.out.println("请输入要进行的操作：1-入队、2-出队，3-查看队列中所有元素。");
        while (scanner.hasNext()) {
            int i = scanner.nextInt();
            switch (i) {
                case 1:
                    System.out.println("请输入要入队的元素：");
                    int x = scanner.nextInt();
                    add(x);
                    break;
                case 2:
                    poll();
                    break;
                case 3:
                    print();
            }
            if (!tap) {
                return;
            }
            System.out.println("请输入要进行的操作：1-入队、2-出队，3-查看队列中所有");
        }
    }

    public static void print() {
        for (int i = 0; i < n; i++) {
            System.out.print(nums[i] + "\t");
        }
        System.out.println();
    }

    private static void priorityQueue() {
        for (int i = n >> 1; i >= 0; i--) {//从队列中所有元素中最后一个分支叶子开始进行下沉操作，即长度除以二的那个位置
            sink(i, n);
        }
    }

    public static void poll() {
        if (n == 0) {
            System.out.println("队列中元素已经全部出队！");
            tap = false;
            return;
        }
        System.out.println("出队元素为：" + nums[0]);
        nums[0] = nums[--n];//把最后一个元素放到队头
        // 然后进行上浮操作
        sink(0, n);
    }

    public static void add(int x) {
        nums[n] = x;//将新入队的元素放到队尾
        swim(n++);//重新进行下称操作
    }

    /**
     * 上浮操作
     *
     * @param i 当前元素索引
     */
    private static void swim(int i) {
        while (i > 0 && nums[i] > nums[i >> 1]) {//如果当前元素不是第一个元素，同时他比他双亲大
            swap(i, i >> 1);//交换上浮
            i >>= 1;//交换完成后当前坐标和其双亲索引下标交换
        }
    }

    private static void sink(int i, int n) {
        while (2 * i < n) {
            int k = 2 * i;
            if (k < n - 1 && nums[k] < nums[k + 1]) {
                k++;
            }
            if (nums[k] <= nums[i]) {
                break;
            } else {
                swap(i, k);
            }
            i = k;
        }
    }

    public static void swap(int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}